
/*
 * Copyright (c) 1999-2008 Mark D. Hill and David A. Wood
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*
 * NonCountingBloomFilter.cc
 *
 * Description:
 *
 *
 */

#include "mem/ruby/filters/H3BloomFilter.hh"
#include "mem/gems_common/Map.hh"
#include "mem/ruby/common/Address.hh"

static int H3[64][16] = {
{
33268410,
395488709,
311024285,
456111753,
181495008,
119997521,
220697869,
433891432,
755927921,
515226970,
719448198,
349842774,
269183649,
463275672,
429800228,
521598937
},
{
628677802,
820947732,
809435975,
1024657192,
887631270,
412050215,
391365090,
324227279,
318338329,
1038393087,
489807930,
387366128,
518096428,
324184340,
429376066,
447109279
},
{
599747653,
404960623,
103933604,
946416030,
656460913,
925957005,
1047665689,
163552053,
88359290,
841315415,
899833584,
1067336680,
348549994,
464045876,
270252128,
829897652
},
{
215495230,
966696438,
82589012,
750102795,
909780866,
920285789,
769759214,
331966823,
939936006,
439950703,
883794828,
1009277508,
61634610,
741444350,
98689608,
524144422
},
{
93868534,
196958667,
774076619,
327921978,
122538783,
879785030,
690748527,
3498564,
83163077,
1027963025,
582088444,
466152216,
312424878,
550064499,
646612667,
561099434
},
{
1002047931,
395477707,
821317480,
890482112,
697094476,
263813044,
840275189,
469664185,
795625845,
211504898,
99204277,
1004491153,
725930417,
1064479221,
893834767,
839719181
},
{
278507126,
985111995,
706462983,
1042178726,
123281719,
963778122,
500881056,
726291104,
134293026,
568379664,
317050609,
533470307,
1022365922,
197645211,
315125721,
634827678
},
{
219227366,
553960647,
870169525,
322232839,
508322497,
648672696,
249405795,
883596102,
476433133,
541372919,
646647793,
1042679515,
43242483,
600187508,
499866821,
135713210
},
{
52837162,
96966684,
401840460,
1071661176,
733560065,
150035417,
341319946,
811582750,
636173904,
519054065,
196321433,
1028294565,
882204070,
522965093,
48884074,
117810166
},
{
650860353,
789534698,
328813544,
473250022,
143128306,
173196006,
846958825,
174632187,
683273509,
405459497,
787235556,
773873501,
240110267,
426797736,
92043842,
711789240
},
{
586637493,
5059646,
398035664,
6686087,
498300175,
948278148,
681227731,
592751744,
572019677,
558044722,
589368271,
695745538,
1073416749,
529192035,
550984939,
1070620580
},
{
102904663,
647598516,
758863940,
313426443,
76504114,
1050747783,
708436441,
563815069,
224107668,
875925186,
167675944,
926209739,
279737287,
1040288182,
768184312,
371708956
},
{
683968868,
1027427757,
180781926,
742898864,
624078545,
645659833,
577225838,
987150210,
723410002,
224013421,
993286634,
33188488,
247264323,
888018697,
38048664,
189037096
},
{
475612146,
426739285,
873726278,
529192871,
607715202,
388486246,
987001312,
474493980,
259747270,
417465536,
217062395,
392858482,
563810075,
137852805,
1051814153,
72895217
},
{
71277086,
785496675,
500608842,
89633426,
274085706,
248467935,
838061983,
48106147,
773662506,
49545328,
9071573,
100739031,
602018002,
904371654,
534132064,
332211304
},
{
401893602,
735125342,
775548339,
210224843,
256081130,
482894412,
350801633,
1035713633,
429458128,
327281409,
739927752,
359327650,
886942880,
847691759,
752417993,
359445596
},
{
267472014,
1050659620,
1068232362,
1049684368,
17130239,
690524969,
793224378,
14455158,
423092885,
873853424,
430535778,
7867877,
309731959,
370260786,
862353083,
403906850
},
{
993077283,
218812656,
389234651,
393202875,
413116501,
263300295,
470013158,
592730725,
441847172,
732392823,
407574059,
875664777,
271347307,
792954404,
554774761,
1022424300
},
{
675919719,
637054073,
784720745,
149714381,
813144874,
502525801,
635436670,
1003196587,
160786091,
947509775,
969788637,
26854073,
257964369,
63898568,
539767732,
772364518
},
{
943076868,
1021732472,
697575075,
15843624,
617573396,
534113303,
122953324,
964873912,
942995378,
87830944,
1012914818,
455484661,
592160054,
599844284,
810394353,
836812568
},
{
688992674,
279465370,
731582262,
687883235,
438178468,
80493001,
342701501,
663561405,
23360106,
531315007,
508931618,
36294623,
231216223,
840438413,
255665680,
663205938
},
{
857265418,
552630887,
8173237,
792122963,
210140052,
823124938,
667709953,
751538219,
991957789,
462064153,
19070176,
726604748,
714567823,
151147895,
1012619677,
697114353
},
{
467105652,
683256174,
702387467,
28730434,
549942998,
48712701,
960519696,
1008345587,
679267717,
370932249,
880419471,
352141567,
331640403,
598772468,
95160685,
812053015
},
{
1053491323,
430526562,
1014938507,
109685515,
765949103,
177288303,
1034642653,
485421658,
71850281,
981034542,
61620389,
601367920,
504420930,
220599168,
583051998,
158735752
},
{
103033901,
522494916,
658494760,
959206022,
931348143,
834510661,
21542994,
189699884,
679327018,
171983002,
96774168,
456133168,
543103352,
923945936,
970074188,
643658485
},
{
566379913,
805798263,
840662512,
820206124,
796507494,
223712542,
118811519,
662246595,
809326534,
416471323,
748027186,
161169753,
739149488,
276330378,
924837051,
964873733
},
{
585882743,
135502711,
3386031,
625631285,
1068193307,
270342640,
432739484,
556606453,
826419155,
1038540977,
158000202,
69109538,
207087256,
298111218,
678046259,
184611498
},
{
305310710,
46237988,
855726974,
735975153,
930663798,
425764232,
104362407,
391371443,
867622101,
71645091,
61824734,
661902640,
293738633,
309416189,
281710675,
879317360
},
{
398146324,
398293087,
689145387,
1038451703,
521637478,
516134620,
314658937,
830334981,
583400300,
340083705,
68029852,
675389876,
994635780,
788959180,
406967042,
74403607
},
{
69463153,
744427484,
191639960,
590927798,
969916795,
546846769,
728756758,
889355646,
520855076,
136068426,
776132410,
189663815,
252051082,
533662856,
362198652,
1026161384
},
{
584984279,
1004834381,
568439705,
834508761,
21812513,
670870173,
1052043300,
341868768,
473755574,
124339439,
36193947,
437997647,
137419489,
58705193,
337793711,
340738909
},
{
898051466,
512792906,
234874060,
655358775,
683745319,
671676404,
428888546,
639928192,
672697722,
176477579,
747020991,
758211282,
443045009,
205395173,
1016944273,
5584717
},
{
156038300,
138620174,
588466825,
1061494056,
1013672100,
1064257198,
881417791,
839470738,
83519030,
100875683,
237486447,
461483733,
681527127,
777996147,
574635362,
815974538
},
{
184168473,
519509808,
62531892,
51821173,
43787358,
385711644,
141325169,
36069511,
584183031,
571372909,
671503175,
226486781,
194932686,
1045460970,
753718579,
331442433
},
{
73065106,
1015327221,
630916840,
1058053470,
306737587,
296343219,
907194989,
920172546,
224516225,
818625553,
551143849,
634570650,
432966225,
756438259,
939564853,
767999933
},
{
884775648,
394862257,
446787794,
219833788,
727195727,
728122304,
249888353,
732947974,
289908868,
448282580,
618161877,
898939716,
739554163,
860631799,
1058977530,
86916736
},
{
143850006,
352708694,
200194048,
979764914,
629404175,
546279766,
72106714,
860980514,
313190585,
897143111,
308425797,
953791785,
349924906,
221457005,
950588925,
908254505
},
{
950032043,
829868728,
68623614,
714624605,
69760597,
297275854,
355894016,
985369737,
882852618,
864071289,
958512902,
950910111,
991368991,
829645051,
434698210,
771350575
},
{
552695074,
319195551,
80297396,
496413831,
944046531,
621525571,
617653363,
416729825,
441842808,
9847464,
99420657,
1033914550,
812966458,
937053011,
673390195,
934577365
},
{
1034695843,
190969665,
332900185,
51897434,
523888639,
883512843,
146908572,
506785674,
565814307,
692255649,
314052926,
826386588,
430691325,
866927620,
413880214,
936474339
},
{
129380164,
741739952,
1013703462,
494392795,
957214600,
1010879043,
931790677,
94551922,
988065869,
120637871,
882506912,
395075379,
210570485,
812422692,
910383687,
817722285
},
{
51850866,
283408630,
1053047202,
858940389,
818507731,
477082181,
353546901,
993324368,
407093779,
231608253,
1067319867,
73159811,
429792535,
971320614,
565699344,
718823399
},
{
408185106,
491493570,
596050720,
310776444,
703628192,
454438809,
523988035,
728512200,
686012353,
976339656,
72816924,
116926720,
165866591,
452043792,
866943072,
968545481
},
{
443231195,
905907843,
1061421320,
746360489,
1043120338,
1069659155,
463359031,
688303227,
186550710,
155347339,
1044842421,
1005904570,
69332909,
706951903,
422513657,
882038450
},
{
430990623,
946501980,
742556791,
278398643,
183759217,
659404315,
279754382,
1069347846,
843746517,
222777670,
990835599,
548741637,
129220580,
1392170,
1032654091,
894058935
},
{
452042227,
751640705,
259481376,
765824585,
145991469,
1013683228,
1055491225,
536379588,
392593350,
913368594,
1029429776,
226857786,
31505342,
1054416381,
32341741,
687106649
},
{
404750944,
811417027,
869530820,
773491060,
810901282,
979340397,
1036910290,
461764404,
834235095,
765695033,
604692390,
452158120,
928988098,
442719218,
1024059719,
167723114
},
{
974245177,
1046377300,
1003424287,
787349855,
336314155,
875074696,
1018462718,
890313003,
367376809,
86355556,
1020618772,
890710345,
444741481,
373230261,
767064947,
840920177
},
{
719581124,
431808156,
138301690,
668222575,
497413494,
740492013,
485033226,
125301442,
831265111,
879071459,
341690480,
152975256,
850330086,
717444507,
694225877,
785340566
},
{
1032766252,
140959364,
737474726,
1062767538,
364464647,
331414723,
356152634,
642832379,
158733632,
374691640,
285504811,
345349905,
876599880,
476392727,
479589210,
606376325
},
{
174997730,
778177086,
319164313,
163614456,
10331364,
599358958,
8331663,
237538058,
159173957,
174533880,
65588684,
878222844,
424467599,
901803515,
187504218,
776690353
},
{
803856182,
965850321,
694948067,
218315960,
358416571,
683713254,
178069303,
428076035,
686176454,
579553217,
357306738,
315018080,
886852373,
568563910,
896839725,
257416821
},
{
401650013,
183289141,
497957228,
879734476,
265024455,
825794561,
889237440,
323359863,
100258491,
991414783,
313986632,
85847250,
362520248,
276103512,
1041630342,
525981595
},
{
487732740,
46201705,
990837834,
62744493,
1067364756,
58015363,
690846283,
680262648,
997278956,
469357861,
432164624,
996763915,
211907847,
167824295,
144928194,
454839915
},
{
41404232,
514493300,
259546924,
578217256,
972345130,
123299213,
346040332,
1014668104,
520910639,
579955198,
36627803,
179072921,
547684341,
598950511,
269497394,
854352266
},
{
603906768,
100863318,
708837659,
204175569,
375560904,
908375384,
28314106,
6303733,
175283124,
749851198,
308667367,
415293931,
225365403,
1032188331,
977112710,
819705229
},
{
399767123,
697985692,
356790426,
643687584,
298624218,
185095167,
381653926,
876816342,
296720023,
2205879,
235816616,
521850105,
622753786,
1021421218,
726349744,
256504902
},
{
851245024,
1022500222,
511909628,
313809625,
99776025,
39710175,
798739932,
741832408,
140631966,
898295927,
607660421,
870669312,
1051422478,
789055529,
669113756,
681943450
},
{
853872755,
491465269,
503341472,
98019440,
258267420,
335602837,
320687824,
1053324395,
24932389,
955011453,
934255131,
435625663,
501568768,
238967025,
549987406,
248619780
},
{
411151284,
576471205,
757985419,
544137226,
968135693,
877548443,
194586894,
74882373,
248353663,
21207540,
273789651,
853653916,
861267970,
533253322,
3739570,
661358586
},
{
271430986,
71390029,
257643671,
949329860,
348156406,
251939238,
445808698,
48269799,
907589462,
105677619,
635451508,
20805932,
464874661,
7542147,
243619464,
288304568
},
{
368215982,
530288964,
770090421,
660961164,
614935537,
630760399,
931299233,
794519275,
779918979,
401746493,
561237006,
1027202224,
258968003,
339508073,
1050610516,
1064307013
},
{
1039172162,
448331205,
928997884,
49813151,
198712120,
992335354,
671024050,
879525220,
745915336,
1038822580,
138669665,
917958819,
681422342,
792868818,
924762727,
816386174
},
{
515190336,
313808618,
441296783,
1022120897,
792325033,
354387581,
59273006,
280075434,
411357221,
665274694,
4054464,
1059046246,
394261773,
848616745,
15446017,
517723271
}};

H3BloomFilter::H3BloomFilter(string str)
{
  //TODO: change this ugly init code...
  primes_list[0] = 9323;
  primes_list[1] = 11279;
  primes_list[2] = 10247;
  primes_list[3] = 30637;
  primes_list[4] = 25717;
  primes_list[5] = 43711;

  mults_list[0] = 255;
  mults_list[1] = 29;
  mults_list[2] = 51;
  mults_list[3] = 3;
  mults_list[4] = 77;
  mults_list[5] = 43;

  adds_list[0] = 841;
  adds_list[1] = 627;
  adds_list[2] = 1555;
  adds_list[3] = 241;
  adds_list[4] = 7777;
  adds_list[5] = 65931;



  string tail(str);
  string head = string_split(tail, '_');

  // head contains filter size, tail contains bit offset from block number
  m_filter_size = atoi(head.c_str());

  head = string_split(tail, '_');
  m_num_hashes = atoi(head.c_str());

  if(tail == "Regular") {
    isParallel = false;
  } else if (tail == "Parallel") {
    isParallel = true;
  } else {
    cout << "ERROR: Incorrect config string for MultiHash Bloom! :" << str << endl;
    assert(0);
  }

  m_filter_size_bits = log_int(m_filter_size);

  m_par_filter_size = m_filter_size/m_num_hashes;
  m_par_filter_size_bits = log_int(m_par_filter_size);

  m_filter.setSize(m_filter_size);
  clear();
}

H3BloomFilter::~H3BloomFilter(){
}

void H3BloomFilter::clear()
{
  for (int i = 0; i < m_filter_size; i++) {
    m_filter[i] = 0;
  }
}

void H3BloomFilter::increment(const Address& addr)
{
  // Not used
}


void H3BloomFilter::decrement(const Address& addr)
{
  // Not used
}

void H3BloomFilter::merge(AbstractBloomFilter * other_filter){
  // assumes both filters are the same size!
  H3BloomFilter * temp = (H3BloomFilter*) other_filter;
  for(int i=0; i < m_filter_size; ++i){
    m_filter[i] |= (*temp)[i];
  }

}

void H3BloomFilter::set(const Address& addr)
{
  for (int i = 0; i < m_num_hashes; i++) {
    int idx = get_index(addr, i);
    m_filter[idx] = 1;

    //Profile hash value distribution
    //g_system_ptr->getProfiler()->getXactProfiler()->profileHashValue(i, idx); // gem5:Arka decomissiong of log_tm
  }
}

void H3BloomFilter::unset(const Address& addr)
{
  cout << "ERROR: Unset should never be called in a Bloom filter";
  assert(0);
}

bool H3BloomFilter::isSet(const Address& addr)
{
  bool res = true;

  for (int i=0; i < m_num_hashes; i++) {
    int idx = get_index(addr, i);
    res = res && m_filter[idx];
  }
  return res;
}


int H3BloomFilter::getCount(const Address& addr)
{
  return isSet(addr)? 1: 0;
}

int H3BloomFilter::getIndex(const Address& addr)
{
  return 0;
}

int H3BloomFilter::readBit(const int index) {
  return 0;
}

void H3BloomFilter::writeBit(const int index, const int value) {

}

int H3BloomFilter::getTotalCount()
{
  int count = 0;

  for (int i = 0; i < m_filter_size; i++) {
    count += m_filter[i];
  }
  return count;
}

void H3BloomFilter::print(ostream& out) const
{
}

int H3BloomFilter::get_index(const Address& addr, int i)
{
  uint64 x = addr.getLineAddress();
  //uint64 y = (x*mults_list[i] + adds_list[i]) % primes_list[i];
  int y = hash_H3(x,i);

  if(isParallel) {
    return (y % m_par_filter_size) + i*m_par_filter_size;
  } else {
    return y % m_filter_size;
  }
}

int H3BloomFilter::hash_H3(uint64 value, int index) {
  uint64 mask = 1;
  uint64 val = value;
  int result = 0;

  for(int i = 0; i < 64; i++) {
    if(val&mask) result ^= H3[i][index];
    val = val >> 1;
  }
  return result;
  }

